package com.leecode;

import java.util.ArrayList;
import java.util.List;

public class Leet78 {
	public static void main(String[] args) {
		new Leet78().subsets(new int[]{1, 2});
	}

	List<List<Integer>> lists = new ArrayList<>();

	/**
	 * 考点:若添加顺序是1,12,123,2,23,3,并利用list.add(Collection)会方便很多,
	 * 若添加顺序是1,2,3,12,23,13,123,则会增加不少难度
	 * 当我第二次写的时候还是没有写出完美的代码,而且还卡壳,所以后来我从backTrace尾部往前推,在这个"往前推理"的过程中
	 * 思考了很多点,觉得对自己帮助很大,所以记录下来当时的思考过程
	 */
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> list=new ArrayList<>();
		if(nums.length==0)return list;
		List<Integer> l=new ArrayList<>();
		backTrace(list,l,0,nums);
		return list;
	}

	/**
	 * 98%,82%,已经要用backTrac
	 * 数字是我思考过程
	 */
	public void backTrace(List<List<Integer>> list,List<Integer> l,int b,int[] nums){//2.1参数列表
		//4.好像不需要退出条件
		//5.应该做点什么,大list加小list,
		//6.List<Integer> l=new ArrayList();//刚开始小list是直接创建的,但一递归就有新的小list,这和后面的回溯对象有严重冲突,
		//7.所以小list应该传入
		//8.list.add(l);//bug:小l一直是同一个对象,并且1.对小l做出改变
		//9.new ArrayList(Collection coll)
		list.add(new ArrayList(l));

		for (int a = b; a < nums.length; a++) {//0.选择列表
			l.add(nums[a]);//1.doSomethind
			backTrace(list,l,a+1,nums);//2.recur,bug:把a+1写成b+1
			l.remove(l.size() - 1);//3.回溯的对象是谁?思考过后,显然回溯的对象应该是小的且为[]的list
		}
	}








	public List<List<Integer>> subsets1(int[] nums) {
		if (nums == null || nums.length == 0) {
			return lists;
		}

		List<Integer> list = new ArrayList<>();
		process(list, nums, 0);
		return lists;

	}

	private void process(List<Integer> list, int[] nums, int start) {
		/**
		 * 刚接触回溯的时候,知道套路后,
		 * 我:先往大list里加,加完后套用回溯套路,又大list移除,所以刚开始我在想:这回溯有球用?加了又删?
		 * 另人:回溯的是小list,而大list是全局的,大list一直在累加,由其是这个 lists.add(Collection col),自已平时用得少
		 * lists.add(new ArrayList(list))
		 */
		lists.add(new ArrayList(list));
		for (int i = start; i < nums.length; i++) {

			list.add(nums[i]);
			process(list, nums, i + 1);
			list.remove(list.size() - 1);
		}
	}

}
